#include <cstdio>
#include <algorithm>
using namespace std;
int Euler(int n){
    int res=n;
    int a=n;
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0){
                a/=i;
            }
        }
    }
    if(a>1){
        res=res/a*(a-1);
    }
    return res;
}
int main(void){
    int n;
    scanf("%d",&n);
    int N,M;
    for(int i=0;i<n;i++){
        scanf("%d%d",&N,&M);
        long long res=0;
        for(int j=1;j*j<=N;j++){
            if(N%j==0){
                if(j*j==N){
                    if(j>=M){
                        //printf("%d\n",j);
                        res+=Euler(N/j);
                    }
                }
                else{
                    if(j>=M){
                        //printf("%d\n",j);
                        res+=Euler(N/j);
                    }
                    if(N/j>=M){
                        //printf("%d\n",j);
                        res+=Euler(j);
                    }
                }
            }
        }
        printf("%lld\n",res);

    }
    return 0;
}